#ifndef _GRAPH_H_
#define _GRAPH_H_

////////////////////////////////////////////////////////////////////////////////
// Includes
////////////////////////////////////////////////////////////////////////////////

#include <vector>
#include "Node.hpp"
#include "TKMacros.h"
#include <iostream>
////////////////////////////////////////////////////////////////////////////////
// Namespaces
////////////////////////////////////////////////////////////////////////////////

namespace Types {

////////////////////////////////////////////////////////////////////////////////
// Implementation
////////////////////////////////////////////////////////////////////////////////

/// Graph exploration directions
typedef enum GraphDirection {
	GD_Forward, GD_Backward, GD_Both
};

/**
 *  Generic Graph
 */
template <typename TN = int, typename TA = int>
class Graph {

	public:

		/// Constructor
		Graph() {}

		/// Create a copy of the given instance
		Graph(const Graph<TN,TA> & inst)
		:	nodes(inst.nodes)
		{}
		
		/// Affectation operator
		Graph & operator = (const Graph<TN,TA> & inst) {
			if (this != &inst)
				this->nodes	= inst.nodes;
			return *this;
		}

		/// Destructor
		virtual ~Graph() {}

		/// Return the number of nodes
		const unsigned int GetNbNodes() const { return this->nodes.size(); }

		/// Returns the required node (read only)
		const Types::Node<TN,TA> & GetNode(const unsigned int i) const { return this->nodes[i]; }

		/// Returns the required nodes
		Types::Node<TN,TA> & Node(const unsigned int i) { return this->nodes[i]; }
		
		/// Adds a node
		virtual const unsigned int AddNode(const Types::Node<TN,TA> & node) { this->nodes.push_back(node); return this->nodes.size()-1; }

		/// Finds the shortest (number of nodes) path between two nodes
		const std::vector<unsigned int> FindShortestPath(
			const unsigned int start,
			const unsigned int end,
			const GraphDirection dir
		) const {
			std::vector<unsigned int> path;
			if ((start >= this->nodes.size()) || (end >= this->nodes.size())) return path;
			return this->find_shortest_path(start, end, dir, path, 0xFFFFFFFF);
		}

		/// Returns the depth of the graph
		const unsigned int Depth() {
			if (this->nodes.empty()) return 0;
			std::vector<unsigned int> path;
			return this->depth(0, path);
		}

		/// Resizes the graph
		virtual void Resize(const unsigned int new_size) {
			this->nodes.resize(new_size);
		}

		/// Clear the graph
		virtual void Clear() { this->nodes.clear(); }

		/// Clear the graph of its arcs
		virtual void ClearArcs() {
			for (unsigned int i=0; i<this->nodes.size(); ++i) this->nodes[i].Clear();
		}
/*
		/// Returns an index list of the super nodes of a given node
		const std::vector<unsigned int> GetSuperNodes(const unsigned int node_idx) const {
			std::vector<unsigned int> super_nodes;
			for (unsigned int n=0; n<this->nodes.size(); ++n)
				for (unsigned int i=0; i<this->nodes[n].GetNbArcs(); ++i)
					if (this->nodes[n].GetArc(i).GetTargetNodeIndex() == node_idx)
						if (std::find(super_nodes.begin(), super_nodes.end(), n) == super_nodes.end())
							super_nodes.push_back(n);
			return super_nodes;
		}
*/
		/// Returns an index list of the sub nodes of a given node
		const std::vector<unsigned int> GetSubNodes(const unsigned int node_idx) const {
			std::vector<unsigned int> sub_nodes;
			for (unsigned int i=0; i<this->nodes[node_idx].GetNbArcs(); ++i)
				if (std::find(sub_nodes.begin(), sub_nodes.end(), this->nodes[node_idx].GetArc(i).GetTargetNodeIndex()) == sub_nodes.end())
					sub_nodes.push_back(this->nodes[node_idx].GetArc(i).GetTargetNodeIndex());
			return sub_nodes;
		}

	protected:

		/// Nodes
		std::vector< Types::Node<TN,TA> > nodes;

		/// Finds the shortest (number of nodes) path between two nodes
		const std::vector<unsigned int> find_shortest_path(
			const unsigned int start,
			const unsigned int end,
			const GraphDirection dir,
			std::vector<unsigned int> & path,
			unsigned int best_length
		) const {
			if (path.size()+1 >= best_length) return std::vector<unsigned int>();
			if (start == end) return std::vector<unsigned int>(1,start);
			std::vector<unsigned int> shortest;
			if ((dir == GD_Forward) || (dir == GD_Both)) {
				for (unsigned int i=0; i<this->nodes[start].GetNbArcs(); ++i) {
					unsigned int n = this->nodes[start].GetArc(i).GetTargetNodeIndex();
					if (std::find(path.begin(), path.end(), n) == path.end()) {
						path.push_back(start);
						std::vector<unsigned int> new_path = this->find_shortest_path(n, end, dir, path, best_length);
						if (!new_path.empty() && (shortest.empty() || (new_path.size() < shortest.size()))) {
							shortest = new_path;
							best_length = path.size() + new_path.size();
						}
						path.pop_back();
					}
				}
			}
			if ((dir == GD_Backward) || (dir == GD_Both)) {
				for (unsigned int n=0; n<this->nodes.size(); ++n) {
					for (unsigned int i=0; i<this->nodes[n].GetNbArcs(); ++i) {
						if (this->nodes[n].GetArc(i).GetTargetNodeIndex() == start) {
							if (std::find(path.begin(), path.end(), n) == path.end()) {
								path.push_back(start);
								std::vector<unsigned int> new_path = this->find_shortest_path(n, end, dir, path, best_length);
								if (!new_path.empty() && (shortest.empty() || (new_path.size() < shortest.size()))) {
									shortest = new_path;
									best_length = path.size() + new_path.size();
								}
								path.pop_back();
							}
							break;
						}
					}
				}
			}
			if (!shortest.empty()) shortest.insert(shortest.begin(), start);
			return shortest;
		}

		const unsigned int depth(const unsigned int idx, std::vector<unsigned int> & path) {
			if (this->nodes[idx].GetNbArcs() == 0) return 0;
			unsigned int max = 0;
			if (std::find(path.begin(), path.end(), idx) == path.end()) {
				for (unsigned int i=0; i<this->nodes[idx].GetNbArcs(); ++i) {
					path.push_back(idx);
					unsigned int d = this->depth(this->nodes[idx].GetArc(i).GetTargetNodeIndex(), path);
					path.pop_back();
					max = MAX(max,d);
				}
			}
			return max + 1;
		}

};

////////////////////////////////////////////////////////////////////////////////
// Closing Namespaces
////////////////////////////////////////////////////////////////////////////////

}

////////////////////////////////////////////////////////////////////////////////

#endif
